package leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * 448. 找到所有数组中消失的数字
 * 给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，
 *
 * 数组中的元素一些出现了两次，另一些只出现一次。
 * <p>
 * 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
 * <p>
 * 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [4,3,2,7,8,2,3,1]
 * <p>
 * 输出:
 * [5,6]
 *
 * 其他见{@link leetcode.a_总结分布.Code02_数组中缺失或重复数字}
 * @date 2020/4/15 14:24
 */
public class Code448_FindAllMissNum {
    //方式1：从1到n对每个数字都从数组中查，时间O(n²),空间O(1)

    //方式2：把存在的数放入hash，从1开始遍历，看哪个不在hash中。时空都是O(n)

    //方式3：标记法
    public List<Integer> findDisappearedNumbers(int[] nums) {
        if(nums == null || nums.length == 0) return new LinkedList<>();
        List<Integer> res=  new LinkedList<>();
        //把1-n标记到 0-n-1位置。因为有的出现1次，有的出现多次，只要出现的，就把位置置负
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) nums[index] = -nums[index];
        }
        //统计正数个数，并还原
        for (int i = 0; i < nums.length; i++) {
            //nums[i]非负，代表nums中不含有 i+1
            if(nums[i] > 0){
                res.add(i+1);
            }else {
                nums[i] = -nums[i];
            }
        }
        return res;
    }
}
